import java.util.LinkedList;
import java.util.Queue;

class Solution1 {
    public int[][] updateMatrix(int[][] mat) {
        int n = mat.length,m = mat[0].length;
        int[][] dist = new int[n][m];
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(mat[i][j] == 0) {
                    dist[i][j] = 0;
                    queue.add(new int[] {i,j});
                }else {
                    dist[i][j] = -1;
                }
            }
        }

        int xx[] = {1,-1,0,0};
        int yy[] = {0,0,1,-1};

        while(!queue.isEmpty()) {
            int[] t = queue.poll();
            int x = t[0], y = t[1];
            for(int i = 0; i<4; i++) {
                int dx = x+xx[i];
                int dy = y+yy[i];
                if(dx>=0 && dx<n && dy>=0 && dy<m && dist[dx][dy]==-1) {
                    queue.add(new int[]{dx,dy});
                    dist[dx][dy] = dist[x][y]+1;
                }
            }
        }

        return dist;
    }
}

class Solution2 {
    public int numEnclaves(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i<n; i++) {
            if(grid[i][0] == 1) {
                queue.add(new int[] {i,0});
            }
            if(grid[i][m-1] == 1) {
                queue.add(new int[] {i,m-1});
            }
        }
        for(int i = 0; i<m; i++) {
            if(grid[0][i] == 1) {
                queue.add(new int[] {0,i});
            }
            if(grid[n-1][i] == 1) {
                queue.add(new int[] {n-1,i});
            }
        }

        int xx[] = {1,-1,0,0};
        int yy[] = {0,0,1,-1};

        while(!queue.isEmpty()) {
            int[] t = queue.poll();
            int x = t[0], y = t[1];
            grid[x][y] = 2;
            for(int i= 0; i<4; i++) {
                int dx = x+xx[i];
                int dy = y+yy[i];
                if(dx>=1 && dx<n && dy>=0 && dy<m && grid[dx][dy] == 1) {
                    queue.add(new int[]{dx,dy});
                    grid[dx][dy] = 2;
                }
            }
        }

        int ret = 0;
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(grid[i][j] == 1) {
                    ret++;
                }
            }
        }
        return ret;
    }
}

class Solution3 {
    public int[][] highestPeak(int[][] isWater) {
        int n = isWater.length, m = isWater[0].length;
        int[][] height = new int[n][m];
        Queue<int[]> queue = new LinkedList<>();
        for(int i= 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(isWater[i][j] == 1) {
                    height[i][j] = 0;
                    queue.add(new int[]{i,j});
                }else {
                    height[i][j] = -1;
                }
            }
        }

        int[] xx = {1,-1,0,0};
        int[] yy = {0,0,1,-1};

        while(!queue.isEmpty()) {
            int[] t = queue.poll();
            int x = t[0], y = t[1];
            for(int i = 0; i<4; i++) {
                int dx = x+xx[i];
                int dy = y+yy[i];
                if(dx>=0 && dx<n && dy>=0 && dy<m && height[dx][dy] == -1) {
                    queue.add(new int[]{dx,dy});
                    height[dx][dy] = height[x][y] + 1;
                }
            }
        }

        return height;
    }
}

class Solution {
    public int maxDistance(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] dist = new int[n][m];
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(grid[i][j] == 1) {
                    dist[i][j] = 0;
                    queue.add(new int[]{i,j});
                }else {
                    dist[i][j] = -1;
                }
            }
        }

        int[] xx = {1,-1,0,0};
        int[] yy = {0,0,1,-1};

        while(!queue.isEmpty()) {
            int[] t = queue.poll();
            int x = t[0], y = t[1];
            for(int i = 0; i< 4; i++) {
                int dx = x + xx[i];
                int dy = y + yy[i];
                if(dx>=0 && dx<n && dy>=0 && dy <m && dist[dx][dy] == -1) {
                    dist[dx][dy] = dist[x][y] + 1;
                    queue.add(new int[]{dx,dy});
                }
            }
        }

        int ret = Integer.MIN_VALUE;
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                ret = Math.max(ret,dist[i][j]);
            }
        }

        if(ret == 0) return -1;
        return ret;
    }
}


public class Test {
}
